#! /usr/bin/env python
import math

class CorePython:
    def calLeap(self, year):
	'''Check a year if it is a leap year.'''
	if (year%4==0 and year%100<>0) or year%400==0:
	    result = True;
	else:
	    result =  False;
	if result==True:
	    print 'Year %d is a leap year.' % year;
	else:
	    print 'Year %d is not a leap year.' % year;
	return result;
    def binSearch(self, li, op):
	leftEnd=0;
	rightEnd=len(li)-1;
	while True:
	    if leftEnd==rightEnd: 
		if op==li[leftEnd]: return True;
		else: return False;
		break;
	    mid=(leftEnd+rightEnd)/2;
	    if op>li[mid]: leftEnd = mid+1;
	    else: rightEnd=mid;
    def isPrime(self, op):
	isPrime=True;
	sqrRoot=int(math.sqrt(op));
	#if op==2: return True;
	for div in range(2,sqrRoot+2):
	    if 0==op%div and div<op: 
		isPrime=False;
		break;
	return isPrime;
    def findPrimeList(self, op):
	liPrime=[];
	for num in range(2,op+1):
	    if self.isPrime(num):
		 liPrime.append(num);
	return liPrime;
    def primeFactorize(self, op1):
	'''Find prime factors for op1.'''
	liPrimeFactors=[];
	sqrRoot=int(math.sqrt(op1));
	#liPrimes=self.findPrimeList(sqrRoot+1);
	liPrimes=self.findPrimeList(op1);
	while True:
	    for div in liPrimes:
		if 0==op1%div: 
		    liPrimeFactors.append(div);
		    op1=op1/div;
		    break;
	    if op1==1: break;
	    if div==liPrimes[len(liPrimes)-1]: break;
	return liPrimeFactors;
    def calGCDAndLCM(self, op1, op2):
	liCommonFactors=[1];
	liPrimeFactors1=self.primeFactorize(op1);
	liPrimeFactors2=self.primeFactorize(op2);
	print liPrimeFactors1;
	print liPrimeFactors2;
	for p in liPrimeFactors2:
	    if True==self.binSearch(liPrimeFactors1, p): 
		liPrimeFactors1.remove(p);
		liCommonFactors.append(p);
	product=1;
	lcm = 1;
	for f in liCommonFactors:
	    product*=f;
	self.gcd = product;
	self.lcm = product * (op1/product) * (op2/product);
	#max1=liPrimeFactors1[len(liPrimeFactors)-1];
	#max2=liPrimeFactors2[len(liPrimeFactors)-1];
	#maxNum=max(max1, max2);
    def main(self):
	#year_ = raw_input('Enter the year: ');
	#year = int(year_);
	#self.calLeap(year);

	li=[1,2,3,4];
	if self.binSearch(li, 3)==True:
	    print 'Found';
	else:
	    print 'Not found.';
	#l=self.findPrimeList(21);
	#l=self.primeFactorize(21);
	#print l;
	op1=int(raw_input('Enter Integer 1 for GCD computation:' ));
	op2=int(raw_input('Enter Integer 2 for GCD computation:' ));
	self.calGCDAndLCM(op1, op2);
	print 'For %d and %d, GCD and LCM are: %d, %d' % (op1,op2, self.gcd, self.lcm);
if __name__=='__main__':
    corePython=CorePython();
    corePython.main();

